package solution.tree;

import common.TreeNode;
import common.util.TreeNodeUtil;

/**
 * @author : wenchao.long
 * @date : Created in 2021/7/13 10:05 周二
 * @description : 将有序数组转换为二叉搜索树
 *         nums已经按照升序排列 高度平衡 二叉搜索树
 *         每个节点的左右两个子树的高度差的绝对值不超过1
 */
public class SortedArrayToBstSolution {

    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = helper(nums, left, mid - 1);
        node.right = helper(nums, mid + 1, right);
        return node;
    }

    public static void main(String[] args) {
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode treeNode = new SortedArrayToBstSolution().sortedArrayToBST(nums);
        TreeNodeUtil.levelOrderList(treeNode);
    }
}
